package day02;

import java.util.Stack;


public class BinaryTree {

    // 先序遍历
    public static void preOrder(Node head){
        System.out.println(head);

        // 递归左树
        if (head.getLeft() != null){
            preOrder(head.getLeft());
        }

        // 递归右树
        if (head.getRight() != null){
            preOrder(head.getRight());
        }
    }

    // 中序遍历
    public static void infixOrder(Node head){

        if (head.getLeft() != null){
            infixOrder(head.getLeft());
        }

        System.out.println(head);

        if (head.getRight() != null){
            infixOrder(head.getRight());
        }

    }

    // 后续遍历
    public static void afterOrder(Node head){
        if (head.getLeft() != null){
            afterOrder(head.getLeft());
        }

        if (head.getRight() != null){
            afterOrder(head.getRight());
        }

        System.out.println(head);
    }

    /**
     * 先序遍历查找元素
     * @param head  二叉树 头结点
     * @param target  查找目标值
     * @return  返回目标节点  如果没有返回 null
     */
    public static Node preOrderSearch(Node head, String target){
        System.out.println("比较中...");
        if (head.getVal().equals(target)){
            return head;
        }

        Node result = null;

        if (head.getLeft() != null){
            result = preOrderSearch(head.getLeft(), target);
        }
        if (result != null){
            return result;
        }
        if (head.getRight() != null){
            result = preOrderSearch(head.getRight(), target);
        }

        return result;
    }


    /**
     * 非递归方式 实现先序遍历
     */
    public static void preByStack(Node head){
        if (head != null){
            Stack<Node> stack = new Stack<>();
            stack.add(head);
            while (!stack.isEmpty()){
                Node pop = stack.pop();
                System.out.print(pop.getVal());  // 头
                if (pop.getRight() != null){    // 右 压栈
                    stack.add(pop.getRight());
                }

                if (pop.getLeft() != null){  // 左 压栈
                    stack.add(pop.getLeft());
                }
            }
        }
    }

    /**
     *  非递归方式 实现 后序遍历
     *     在先序遍历的基础上 改为  头 右 左  放入栈中  在输出  就是 左右头
     */
    public static void afterByStack(Node head){
        if (head != null){
            Stack<Node> stack = new Stack<>();
            Stack<Node> aflterStack = new Stack<>();
            stack.add(head);
            while (!stack.isEmpty()){
                Node pop = stack.pop();
                aflterStack.add(pop);

                if (pop.getLeft() != null){
                    stack.add(pop.getLeft());
                }
                if (pop.getRight() != null){
                    stack.add(pop.getRight());
                }
            }

            print(aflterStack);
        }
    }

    private static void print(Stack<Node> aflterStack) {
        while (!aflterStack.isEmpty()){
            System.out.println(aflterStack.pop().getVal());
        }
    }


    /**
     * 递归删除节点
     *    如果删除的是叶子节点，则删除该节点
     *    如果删除的节点是非叶子节点，则删除该子树
     * @param head   要操作的二叉树
     * @param delVal  要删除的节点数据值
     */
    public static void delNode(Node head, String delVal){
        if (head.getLeft() != null && head.getLeft().getVal().equals(delVal)){
            head.setLeft(null);
            return;
        }

        if (head.getRight() != null && head.getRight().getVal().equals(delVal)){
            head.setRight(null);
            return;
        }

        if (head.getLeft() != null){
            delNode(head.getLeft(), delVal);
        }

        if (head.getRight() != null){
            delNode(head.getRight(), delVal);
        }
    }


    public static void main(String[] args) {
        Node head = CreateTree.createTree();
         preOrder(head);
//        infixOrder(head);
//        afterOrder(head);

//        Node s = preOrderSearch(head, "s");
//        System.out.println(s);

//        preByStack(head);
            afterByStack(head);
    }
}


